package com.year_23.april;

import java.util.*;

import static jdk.nashorn.internal.objects.NativeMath.random;

/**
 *  https://leetcode.cn/problems/online-majority-element-in-subarray/submissions/
 *  1157  子数组中站大多数的元素
 *
 * @Author jsh
 * @Date 2023/4/15 23:59
 * @Version 1.0
 */
public class Day16 {
    public static void main(String[] args) {
        /*[[[1,1,2,2,1,1]],[0,5,4],[0,3,3],[2,3,2]]*/
        int[] arr = {1,1,2,2,1,1};
        MajorityChecker majorityChecker = new MajorityChecker(arr);
        System.out.println(majorityChecker.query(2, 3, 2));
    }
}
/*
*  随机法 + 二分查找
* */
class MajorityChecker {

    public static final int K = 20;
    private int[] arr;
    private Map<Integer, List<Integer>> loc;
    private Random random;

    public MajorityChecker(int[] arr) {
        this.arr = arr;
        this.loc = new HashMap<Integer, List<Integer>>();
        //数组中数值出现的索引值
        for (int i = 0; i < arr.length; i++) {
            loc.putIfAbsent(arr[i], new ArrayList<>());
            loc.get(arr[i]).add(i);
        }
        random = new Random();
    }

    public int query(int left, int right, int threshold) {
        int l = right - left + 1;
        for (int i = 0; i < K; i++) {
            int x = arr[left + random.nextInt(l)];
            List<Integer> list = loc.get(x);
            //x在[left,right] 中出现的次数
            int y = searchEnd(list, right) - searchStart(list, left);
            if (y >= threshold){
                return x;
            }else if ( y*2 > l){
                return -1;
            }
        }
        return -1;
    }
    /*
    * list代表的值,在数值arr中从0到left 位置（不包括）有多少个
    *
    * *@Author cxx
    * @date 22:15 2023/4/16
    * @Param
    * @return
    **/
    private int searchStart(List<Integer> list, int target){
        int low = 0, high = list.size();
        while (low < high){
            int mid = low + (high - low)/2;
            if (list.get(mid) >= target){
                high = mid;
            }else {
                low = mid +1;
            }
        }
        return low;
    }

    //list代表的值，在数值arr中从0到right 位置（包括）有多少个
    private int searchEnd(List<Integer> list, int target){
        int low = 0, high = list.size();
        while (low < high){
            int mid = low + (high - low)/2;
            if (list.get(mid) > target){
                high = mid;
            }else {
                low = mid + 1;
            }
        }
        return low;
    }
}